﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/partition-list-lcci/
/*
题目描述：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
*/


 // Definition for singly-linked list.
 struct ListNode {
     int val;
     struct ListNode *next;
  };

 struct ListNode* partition(struct ListNode* head, int x) {
     struct ListNode* LessHead = NULL;
     struct ListNode* LessHeadTail = NULL;
     struct ListNode* GreatHead = NULL;
     struct ListNode* GreatHeadTail = NULL;
     struct ListNode* cur = head;
     while (cur) {
         if (cur->val < x) {
             if (NULL == LessHead) {
                 LessHead = cur;
                 LessHeadTail = LessHead;
             }
             else {
                 LessHeadTail->next = cur;
                 LessHeadTail = LessHeadTail->next;
             }
         }
         else {
             if (NULL == GreatHead) {
                 GreatHead = cur;
                 GreatHeadTail = cur;
             }
             else {
                 GreatHeadTail->next = cur;
                 GreatHeadTail = cur;
             }
         }
         cur = cur->next;
     }
     GreatHeadTail->next = NULL;
     LessHeadTail->next = GreatHead;
     return LessHeadTail;
 }